package com.fang.find;

public class KMP {

	public boolean kmp(String A, String B, int[] next) {
		return kmp(A.toCharArray(),B.toCharArray(),next);
	}
	
	public boolean kmp(char[] A, char[] B, int[] next) {
		int aCount = 0;
		int bCount = 0;

		while (bCount < B.length && aCount < A.length) {
			if (A[aCount] == B[bCount]) {
				aCount++;
				bCount++;
				if (bCount == B.length)
					return true;
			} else {
				int tempNext = next[bCount];
				if (tempNext == -1) {
					if(bCount == 0){
						aCount++;
					}
					bCount = 0;
					
				} else {
					bCount = tempNext;
				}
			}
		}
		return false;
	}
	
	public static  int[] getNext(String ps)
	{
	    char[] strKey = ps.toCharArray();
	    int[] next = new int[strKey.length];

	    // 初始条件
	    int j = 0;
	    int k = -1;
	    next[0] = -1;
	 
	    // 根据已知的前j位推测第j+1位
	    while (j < strKey.length - 1)
	    {
	        if (k == -1 || strKey[j] == strKey[k])
	        {
	            next[++j] = ++k;
	        }
	        else
	        {
	            k = next[k];
	        }
	    }
	     return next;
	}
	
//	public int[] calNext(char[] str, int len) {
//		int i = 0, j = 0;
//		int[] next = new int[len];
//		next[0] = -1;
//		while(i< len-1) {
//			j = next[i];
//			while ((j >= 0) && (str[j] != str[i]) ) {
//				j = next[j];
//			}
//			if ((j >= 0) && (str[i] == str[j])) {
//				next[++i] = j + 1;
//			} else {
//				next[++i] = 0;
//			}
//		}
//		return next;
//	
//	}
}
